package leetcode.hot100;

import leetcode.common.ListNode;

@SuppressWarnings("all")
public class _148_排序链表_归并算法和合并链表 {

    // 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表
    // 要求在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        // 从题目要求：排序+时间复杂度的限制，我们想到使用归并排序算法可以满足

        // 找到中心结点对半分链表
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // slow指向链表中心结点
        ListNode nextHead = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(nextHead);

        // 合并链表并排序
        // 转换为合并两个升序链表的逻辑
        ListNode dummyNode = new ListNode(0);
        ListNode node = dummyNode;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                node.next = left;
                left = left.next;
            } else {
                node.next = right;
                right = right.next;
            }
            node = node.next;
        }
        // 合并的链表长度不一定相同，那么还未遍历完的部分直接接在新建的链表末尾
        node.next = left == null ? right : left;
        return dummyNode.next;
    }
}
